// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

// 快排
var findKthLargest = function (nums, k) {
  const len = nums.length;
  const targetIndex = len - k;    // 第k大的元素的下标
  let left = 0,
      right = len - 1;

  while (left < right) {
    const index = partition(nums, left, right);   // 将数组分成两部分，一部分比targetIndex大，一部分比targetIndex小
    if (index === targetIndex) {   // 如果index等于targetIndex，说明targetIndex在这个数组中的位置已经找到了
      return nums[index];  // 返回targetIndex
    } else if (index < targetIndex) { // 如果index小于targetIndex，说明targetIndex在这个数组中的位置还没找到，那么targetIndex应该在右边的数组中
      left = index + 1;   // 将targetIndex的左边界向右移动一位
    } else {
      right = index - 1;  // 将targetIndex的右边界向左移动一位
    }
  }

  return nums[left];
};

function partition(nums, start, end) {   // 快排的分区函数
  const povit = nums[start];   // 取第一个元素作为基准元素
  while (start < end) {  // 将数组分成两部分，一部分比povit大，一部分比povit小
    // 将数组中比povit大的元素放在右边，比povit小的元素放在左边
    while (start < end && nums[end] >= povit) {// 将数组中比povit大的元素放在右边
      end--;  // 将数组中比povit大的元素放在右边
    }
    nums[start] = nums[end];  // 将比povit小的元素交换到左边   nums[start] = nums[end] 不会覆盖之前的start值吗？   因为start是一个变量，所以可以被修改
    while (start < end && nums[start] < povit) {  // 将数组左边的元素全部与povit比较，一旦发现比povit大的，就将其交换到右边
      start++;  // 将左边的元素向右移动一位
    }
    nums[end] = nums[start];    // 将比povit大的元素交换到右边
  }
  nums[start] = povit;  // 将povit放到正确的位置
  return start; // 返回povit的位置
}


console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));